//
// Created by Administrator on 2021/5/10.
//
#include <string>
#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    int minAddToMakeValid(string S) {
        if (S.empty()) return 0;
        stack<char> stk;
        for (const auto &ch : S) {
            if (ch == '(') stk.push(ch);
            else {
                if (!stk.empty() and stk.top() == '(') stk.pop();
                else stk.push(ch);
            }
        }
        return static_cast<int>(stk.size());
    }
};

class Solution2 { // 优秀题解  平衡法
public:
    int minAddToMakeValid(string S) {
        int nRight = 0;
        int nLeft = 0;
        for (char ch : S) {
            if (ch == ')') { // 遇到')'
                if (nLeft == 0) { // 前面的括号是左右平衡的
                    nRight++;
                    continue;
                } else {
                    nLeft--; // 前面有未配对的左括号'('
                }
            } else { // 遇到'('
                nLeft++;
            }
        }

        return nRight + nLeft;
    }
};

int main() {
    Solution2 sol;
    cout << sol.minAddToMakeValid("())") << endl;
    cout << sol.minAddToMakeValid("(((") << endl;
    cout << sol.minAddToMakeValid("()") << endl;
    cout << sol.minAddToMakeValid("()))((") << endl;
    return 0;
}